class Solution:

    # 方法一：dp

    # def longestValidParentheses(self, s: str) -> int:
    #     n = len(s)
    #     if n == 0:
    #     return 0
    #     dp = [0] * n
    #     for i in range(n):
    #         if s[i]==')' and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(':
    #             dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
    #     return max(dp)

    # 方法二：栈
    def longestValidParentheses2(self, s: str) -> int:
        n = len(s)
        myStack = [-1]
        if n == 0:
            return 0
        length = maxLen = 0
        for i in range(n):
            if s[i] == '(':
                myStack.append(i)
            else:
                myStack.pop()
                if not myStack:
                    myStack.append(i)
                else:
                    length = i - myStack[-1]
                    maxLen = max(maxLen, length)
            print(myStack)
        return maxLen


if __name__ == "__main__":
    mySol = Solution()
    al = [1, 2, 3, 2, 1, 0, 1]
    bl = [3, 2, 1, 0, 1, 4, 7]
    mystr = '())(())'
    # al = [0, 0, 0, 0, 1]
    # bl = [1, 0, 0, 0, 0]
    print('feedback:', mySol.longestValidParentheses2(mystr))
